package Leetcode.LeetcodeDemo1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;


public class LeetCode23 {
    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    public static ListNode mergeKLists(ListNode[] lists) {
        ArrayList<ListNode> alist = new ArrayList<ListNode>();
        for (int i = 0; i < lists.length; i++) {
            ListNode cur = lists[i];
            ListNode tmp = null;
            while (cur != null) {
                tmp = cur.next;
                cur.next = null;
                alist.add(cur);
                cur = tmp;
            }
        }
        ListNode[] newList=new ListNode[alist.size()];
        for (int i = 0; i < newList.length; i++) {
            newList[i]=alist.get(i);
        }
        Arrays.sort(newList, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val-o2.val;
            }
        });
        ListNode head=null;
        ListNode cur=null;
        for (int i = 0; i < newList.length; i++) {
            if(head==null){
                head=newList[i];
                cur=newList[i];
            }else{
                cur.next=newList[i];
                cur=newList[i];
            }
        }
        return head;
    }



    public static void main(String[] args) {
         ListNode n1=new ListNode(1);
         ListNode n2=new ListNode(4);
         ListNode n3=new ListNode(5);
         ListNode a1=new ListNode(1);
         ListNode a2=new ListNode(3);
         ListNode a3=new ListNode(4);
         n1.next=n2;
         n2.next=n3;
         n3.next=null;
         a1.next=a2;
         a2.next=a3;
         a3.next=null;
         ListNode c1=new ListNode(1);
         ListNode[] list={c1};
        ListNode listNode = mergeKLists(list);
        while(listNode!=null){
            System.out.print(listNode.val+" ");
            listNode=listNode.next;
        }
    }
}
